// public class Test {
//     public static void main(String[] args) {
//         String str = "";
//         System.out.println(str);
//     }
// }

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

//! ver1
// class Solution {
//     public String tree2str(TreeNode root) {
//         if (root == null) {
//             return "";
//         }

//         StringBuilder str = new StringBuilder();
//         str.append(root.val);

//         if (root.left != null) {
//             str.append('(');
//             str.append(tree2str(root.left));
//             str.append(')');
//         } else if (root.right != null) {
//             str.append("()");
//         }

//         if (root.right != null) {
//             str.append('(');
//             str.append(tree2str(root.right));
//             str.append(')');
//         }

//         return str.toString();
//     }
// }

//! ver2
// class Solution {
//     private StringBuilder sb = new StringBuilder();
//     public String tree2str(TreeNode root) {
//         _tree2str(root);
//         return sb.substring(1, sb.length() - 1);
//     }

//     public void _tree2str(TreeNode root) {
//         sb.append('(');
//         sb.append(root.val);
//         if (root.left != null) _tree2str(root.left);
//         else if (root.right != null) sb.append("()");
//         if (root.right != null) _tree2str(root.right);
//         sb.append(')');
//     }
// }